1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
#define int long long
using namespace std;
inline int read(){
int w=0,x=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return w?-x:x;
}
namespace star
{
const int maxn=1e5+10,maxm=3e5+10,INF=0x3f3f3f3f3f3f3f3f;
int n,m;
struct Edge{
int u,v,dis;
bool is;
inline bool operator <(const Edge &zp)const {return dis<zp.dis;}
}e[maxm];
int ecnt,head[maxn],to[maxn<<1],Fa[maxn],nxt[maxn<<1],v[maxn<<1],ans=INF,sum,fa[maxn][25],mx[maxn][25],pmx[maxn][25],dep[maxn];
inline int find(int x){return Fa[x]==x?x:Fa[x]=find(Fa[x]);}
inline void addedge(int a,int b,int c){
to[++ecnt]=b,nxt[ecnt]=head[a],head[a]=ecnt,v[ecnt]=c;
to[++ecnt]=a,nxt[ecnt]=head[b],head[b]=ecnt,v[ecnt]=c;
}
inline void kruskal(){
for(int i=1;i<=n;i++)Fa[i]=i;
sort(e+1,e+1+m);
int cnt=0;
for(int i=1;i<=m;i++){
int fx=find(e[i].u),fy=find(e[i].v);
if(fx!=fy){
Fa[fx]=fy;
addedge(e[i].u,e[i].v,e[i].dis);
e[i].is=1;
sum+=e[i].dis;
if(++cnt==n-1)break;
}
}
}
void dfs(int x,int f){
fa[x][0]=f;
dep[x]=dep[f]+1;
for(int i=0;i<=20;i++){
fa[x][i+1]=fa[fa[x][i]][i];
mx[x][i+1]=max(mx[x][i],mx[fa[x][i]][i]);
if(mx[x][i+1]!=mx[x][i])pmx[x][i+1]=max(pmx[x][i+1],mx[x][i]);
if(mx[x][i+1]!=mx[fa[x][i]][i])pmx[x][i+1]=max(pmx[x][i+1],mx[fa[x][i]][i]);
if(mx[x][i+1]!=pmx[x][i])pmx[x][i+1]=max(pmx[x][i+1],pmx[x][i]);
if(mx[x][i+1]!=pmx[fa[x][i]][i])pmx[x][i+1]=max(pmx[x][i+1],pmx[fa[x][i]][i]);
}
for(int i=head[x];i;i=nxt[i]){
int u=to[i];
if(u==f)continue;
mx[u][0]=v[i];
dfs(u,x);
}
}
inline void LCA(int x,int y,int &mxx,const int &MX){
if(dep[x]<dep[y])swap(x,y);
for(int i=20;i+1;i--)if(dep[fa[x][i]]>=dep[y]){
if(mx[x][i]!=MX)mxx=max(mxx,mx[x][i]);
else mxx=max(mxx,pmx[x][i]);
x=fa[x][i];
}
if(x==y)return;
for(int i=20;i+1;i--)if(fa[x][i]!=fa[y][i]){
if(mx[x][i]!=MX)mxx=max(mxx,mx[x][i]);
else mxx=max(mxx,pmx[x][i]);
x=fa[x][i];
if(mx[y][i]!=MX)mxx=max(mxx,mx[y][i]);
else mxx=max(mxx,pmx[y][i]);
y=fa[y][i];
}
if(mx[x][0]!=MX)mxx=max(mxx,mx[x][0]);
else mxx=max(mxx,pmx[x][0]);
if(mx[y][0]!=MX)mxx=max(mxx,mx[y][0]);
else mxx=max(mxx,pmx[y][0]);
}
inline void work(){
n=read(),m=read();
for(int i=1;i<=m;i++)e[i].u=read(),e[i].v=read(),e[i].dis=read();
kruskal();
dfs(1,0);
for(int i=1;i<=m;i++)if(!e[i].is){
int x=e[i].u,y=e[i].v,MX=-INF;
LCA(x,y,MX,e[i].dis);
ans=min(ans,sum-MX+e[i].dis);
}
printf("%lld",ans);
}
}
signed main(){
star::work();
return 0;
}
|
